# 钢条切割问题（最优子结构）：钢条长度不同价格也不同，n长的钢条如何买更多的钱？
# 自底向下
# O(n^2)
def cut_rod_dp(p, n):
	r = [0]
	for i in range(1,n+1):
		res = 0
		for j in range(1,i+1):
			res = max(res,p[j] + r[i-j])
		r.append(res)
	return  r[n]


# 最长公共子序列LCS
# eg： ABCD 和 BDF 都是 ABCDEFG 的子序列
# 例：x = 'ABBCBDE' Y = 'DBBCDB' LCS(X,Y) = 'BBCD'




#扩展：欧几里得算法求最大公约数

def gcd(a,b):
	if b == 0:
		return a
	else:
		return gcd(b, a%b)


def gcd2(a,b):  
	while b > 0:
		a,b = b,a % b
	return a
# print(gcd2(12,18))
































